\chapter{Various}

\section{Dynamic programming}

When doing DP on intervals: $a[i][j] = \min_{i < k < j}(a[i][k] + a[k][j]) + f(i, j)$, where the (minimal) optimal $k$ increases with both $i$ and $j$,
\begin{itemize}
\item one can solve intervals in increasing order of length, and search $k = p[i][j]$ for $a[i][j]$ only between $p[i][j-1]$ and $p[i+1][j]$.
\item This is known as Knuth DP. Sufficient criteria for this are if $f(b,c) \le f(a,d)$ and $f(a,c) + f(b,d) \le f(a,d) + f(b,c)$ for all $a \le b \le c \le d$.
\item Consider also: LineContainer (ch. Data structures), monotone queues, ternary search.
\end{itemize}

	\kactlimport{CircularLCS.h}
	\kactlimport{SMAWK.h}

\section{Debugging tricks}
	\begin{itemize}
		\item \texttt{signal(SIGSEGV, [](int) \{ \_Exit(0); \});} converts segfaults into Wrong Answers.
			Similarly one can catch SIGABRT (assertion failures) and SIGFPE (zero divisions).
			\texttt{\_GLIBCXX\_DEBUG} violations generate SIGABRT (or SIGSEGV on gcc 5.4.0 apparently).
		\item \texttt{feenableexcept(29);} kills the program on NaNs (\texttt 1), 0-divs (\texttt 4), infinities (\texttt 8) and denormals (\texttt{16}).
	\end{itemize}

\section{Optimization tricks}
	\subsection{Bit hacks}
		\begin{itemize}
			\item \texttt{x \& -x} is the least bit in \texttt{x}.
			\item \texttt{for (int x = m; x; ) \{ --x \&= m; ... \}} loops over all subset masks of \texttt{m} (except \texttt{m} itself).
			\item \texttt{c = x\&-x, r = x+c; (((r\^{}x) >> 2)/c) | r} is the next number after \texttt{x} with the same number of bits set.
			\item \texttt{ F0R(b,k) F0R(i,1<<K) if (i\&1<<b) D[i] += D[i\^{}(1<<b)]; } computes all sums of subsets.
		\end{itemize}
	\subsection{Pragmas}
	
		\begin{itemize}
			\item \lstinline{#pragma GCC optimize ("Ofast")} will make GCC auto-vectorize for loops and optimizes floating points better (assumes associativity and turns off denormals).
			\item \lstinline{#pragma GCC target ("avx,avx2")} can double performance of vectorized code, but causes crashes on old machines. Also consider older \lstinline{#pragma GCC target ("sse4")}.
			\item \lstinline{#pragma GCC optimize ("trapv")} kills the program on integer overflows (but is really slow).
		\end{itemize}

	% \kactlimport{BumpAllocator.h}
	% \kactlimport{SmallPtr.h}
	% \kactlimport{BumpAllocatorSTL.h}
	\kactlimport{FastIO.h}

\section{Other languages}
	% \kactlimport{Main.java}
	\kactlimport{Python3.py}
	\kactlimport{Decimal.py}
	% \kactlimport{Kotlin.kt}